// m
// 给定一个整数数组nums，设计算法来打乱一个没有重复元素的数组，打乱后，数组的所有排列应该是等可能的
// 实现Solution 类，使用整数数组nums初始化对象
// reset，重设数组到它的初始状态并返回
// shuffle，返回数组随机打乱后的结果

// 思路：洗牌算法
// 对于长度为n的数组，我们可以把问题转换为：分别在n个位置，选择填入某个数的概率是相同
// 对于每个位置被选中的概率都是1/n
// 对于第0个位置，我们从0，n-1中n个数中选择一个，与0位置交换， 1/n
// 对于第1个位置，我们从1，n-1中n-1个数中选中一个，与1位置交换, n-1/n * 1/n-1 = 1/n
// 对于第2个位置，我们从2，n-1中n-2个数中选中一个，与2位置交换, n-1/n * n-2/n-1 * 1/n-1 = 1/n
// 依次类推

class Solution {
    constructor(nums) {
        this.init(nums)
    }
    init(nums) {
        this.nums = nums
    }

    reset() {
        return this.nums
    }

    shuffle() {
        this.shuffleNums = this.nums.slice(0)
        for (let i = 0; i < this.shuffleNums.length; i++) {
            let swapIndex = Math.floor(Math.random() * (this.shuffleNums.length - i)) + i;
            [this.shuffleNums[i], this.shuffleNums[swapIndex]] = [this.shuffleNums[swapIndex], this.shuffleNums[i]]
        }
        return this.shuffleNums
    }
}

let arr = [1,2,3,4,5]
let solution = new Solution(arr)
console.log(solution.shuffle());
console.log(solution.reset());

